int getBlack(QImage *image, int x, int y) {
	if (x < 0 || x >= image->width())
		return 0;
	if (y < 0 || y >= image->height())
		return 0;

	int px = qRed(image->pixel(x,y));
	if (px == 0)
		return 1;
	return 0;
}

int isHole(QImage *orig, QImage *dest, int x, int y) {
	if (x < 0 || x >= orig->width())
		return 0;
	if (y < 0 || y >= orig->height())
		return 0;
	if (((int)qRed(orig->pixel(x,y))) == 0)
	   	return 0;
	if (((int)qRed(dest->pixel(x,y))) == 0)
	   	return 0;

	
	if (getBlack(dest, x+1, y))
	   	return 1;
	if (getBlack(dest, x-1, y))
	   	return 1;
	if (getBlack(dest, x, y+1))
	   	return 1;
	if (getBlack(dest, x, y-1))
	   	return 1;
   	return 0;
}
void fillHole(QImage *orig, QImage *dest, int x1, int y1) {
	for( int y = 0; y < orig->height(); ++y ){
		for( int x = 0; x < orig->width(); ++x ){
		   dest->setPixel(x, y, QColor(255,255,255).rgb());
		}
	}
	dest->setPixel(x1, y1, QColor(0,0,0).rgb());

	int changed = 1;
	for (int i=0; changed == 1 && i<1000; i++) { //1000 é so uma protecao
	   changed = 0;
	   for( int y = 0; y < orig->height(); ++y )
		  for( int x = 0; x < orig->width(); ++x )
			 if (isHole(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int x = 0; x < orig->width(); ++x )
		  for( int y = 0; y < orig->height(); ++y )
			 if (isHole(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int y = orig->height()-1; y >= 0; --y )
		  for( int x = orig->width(); x>=0; --x )
			 if (isHole(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int x = orig->width(); x>=0 ; --x )
		  for( int y = orig->height()-1; y >= 0; --y )
			 if (isHole(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	}
}

void fillHoles(QImage *orig, QImage *dest) {
   	int stop = 0;
	QImage *tmp = new QImage( orig->width(), orig->height(), QImage::Format_RGB32 );
	for( int y = 0; !stop && y < orig->height(); ++y ){
		for( int x = 0; !stop && x < orig->width(); ++x ){
		   int px = qRed(orig->pixel(x,y));
		   	if (px == 255) {
				fillHole(orig, tmp, x, y);
				stop = 1;
			}
		}
	}

	for( int y = 0; y < orig->height(); ++y ){
		for( int x = 0; x < orig->width(); ++x ){
			int px = qRed(orig->pixel(x,y));
			if (px == 0 || ((int)qRed(tmp->pixel(x,y))) == 255)
			   dest->setPixel(x, y, QColor(0,0,0).rgb());
			else
			   dest->setPixel(x, y, QColor(255,255,255).rgb());
		}
	}

}

void NewspaperSegmentation::computeStep4Image(){
	if( image_step[3] == 0 )
		computeStep3Image();
	if( image_step[4] ){
		setCurrentImage( 4 );
		return;
	}

	QImage *tmp = new QImage( image_step[3]->width(), image_step[3]->height(), QImage::Format_RGB32 );
	for( int y = 0; y < image_step[3]->height(); ++y ){
		for( int x = 0; x < image_step[3]->width(); ++x ){
			int r = 255;
			int px = getBlack(image_step[3], x,y);
			if (px == 1)
				r = 0;
			else {
				px = 	getBlack(image_step[3], x-1, y+1) +
						getBlack(image_step[3], x-1, y) +
						getBlack(image_step[3], x-1, y-1) +
						getBlack(image_step[3], x, y+1) +
						getBlack(image_step[3], x, y-1) +
						getBlack(image_step[3], x+1, y+1) +
						getBlack(image_step[3], x+1, y) +
						getBlack(image_step[3], x+1, y-1) +
						getBlack(image_step[3], x-2, y) + 
						getBlack(image_step[3], x+2, y) + 
						getBlack(image_step[3], x, y-2) + 
						getBlack(image_step[3], x, y+2); 
				if (px >= 5)
					r = 0;
			}

			//QMessageBox::about ( this, QString("energy"), QString("%1").arg(px));
			tmp->setPixel(x, y, QColor(r,r,r).rgb());
		}
	}

	QImage *tmp2 = new QImage( tmp->width(), tmp->height(), QImage::Format_RGB32 );
	for( int y = 0; y < tmp->height(); ++y ){
		for( int x = 0; x < tmp->width(); ++x ){
			int r = 255;
			int px = getBlack(tmp, x,y);
			if (px == 1)
				r = 0;
			else {
				px = 	getBlack(tmp, x-1, y+1) +
						getBlack(tmp, x-1, y) +
						getBlack(tmp, x-1, y-1) +
						getBlack(tmp, x, y+1) +
						getBlack(tmp, x, y-1) +
						getBlack(tmp, x+1, y+1) +
						getBlack(tmp, x+1, y) +
						getBlack(tmp, x+1, y-1) +
						getBlack(tmp, x-2, y) + 
						getBlack(tmp, x+2, y) + 
						getBlack(tmp, x, y-2) + 
						getBlack(tmp, x, y+2); 
				if (px >= 5)
					r = 0;
			}

			//QMessageBox::about ( this, QString("energy"), QString("%1").arg(px));
			tmp2->setPixel(x, y, QColor(r,r,r).rgb());
		}
	}

	fillHoles(tmp2, tmp);
	
	image_step[4] = new QImage( tmp->width(), tmp->height(), QImage::Format_RGB32 );
	for( int y = 0; y < tmp->height(); ++y ){
		for( int x = 0; x < tmp->width(); ++x ){
		   	int r = qRed(tmp->pixel(x,y));
			image_step[4]->setPixel(x, y, QColor(r,r,r).rgb());
		}
	}
	//image_step[4]->save("/tmp/bla.png", "png");
	
	//término da implementação
	setCurrentImage( 4 );
}
